#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int DataType; 

typedef struct node { 
	DataType data; 
	struct node * next; 
} LinkNode, * LinkList; 


LinkNode *__creat_node(const DataType data);
int list_init(LinkList * mylist);
int list_insert(LinkList mylist, const DataType data);
int __is_empty(LinkList mylist);
int list_del(LinkList mylist, DataType key);
void list_destroy(LinkList *mylist);
void list_show(LinkList mylist);
LinkList list_reverse(LinkList mylist);
int list_del_max(LinkList mylist);
DataType * two_list_repeat(LinkList list1, LinkList list2, int *num);


int main(void) {
    LinkList list;
	LinkList list2;
	DataType *arr = NULL;
	int num = 0;

    if (list_init(&list) != 0) {
        printf("链表1初始化失败\n");
        return -1;
    } 
	if (list_init(&list2) != 0) {
        printf("链表2初始化失败\n");
        return -1;
    }

    
    // 插入测试
    list_insert(list, 1);
    list_insert(list, 2);
    list_insert(list, 3); 
   	list_insert(list, 4);
    list_insert(list, 5);
    list_insert(list, 6);
	list_insert(list, 7);
    list_insert(list, 8);
    list_insert(list, 9);

    printf("插入后链表1：");
    list_show(list); 
    printf("\n");
	
	list_insert(list2, 11);
    list_insert(list2, 21);
    list_insert(list2, 31); 
   	list_insert(list2, 41);
    list_insert(list2, 51);
    list_insert(list2, 61);
	list_insert(list2, 71);
    list_insert(list2, 8);
    list_insert(list2, 9);

    printf("插入后链表2：");
    list_show(list2);
    printf("\n");

    // 删除测试
    if (list_del(list, 2) == 0) {
        printf("list删除2后：");
        list_show(list);
		printf("\n");
    }

	list_del_max(list2);
	printf("删最大list2：");
	list_show(list2);	
	printf("\n");


	list_reverse(list);
	printf("翻转后： ");
	list_show(list);
	printf("\n");

	arr = two_list_repeat(list, list2, &num);
	for(int i = 0; i < num; i++){
		printf("%d ", arr[i]);
	}
	printf("\n");
    
    // 销毁链表
    list_destroy(&list);
	list_destroy(&list2);

    return 0;
}

DataType *add_Ddta(DataType *arr, DataType data, int num){
	DataType *tem = realloc(arr, num * sizeof(DataType));

	if(tmp == NULL){
        free(arr); 
        return NULL;
    }
    arr = tmp;
	arr[num-1] = data;

	return arr;
}

DataType * two_list_repeat(LinkList list1, LinkList list2, int *num){
	if(__is_empty(list1) || __is_empty(list2))
		return NULL;
	DataType * arr = NULL;

	LinkNode *list1_node = list1->next;
	LinkNode *list2_node = list2->next;
	
	while(list1_node != NULL){
		list2_node = list2->next;
		while(list2_node != NULL){
			if(list1_node->data == list2_node->data){
				(*num)++;
				DataType *tmp = add_Ddta(arr, list2_node->data, *num);
                if(tmp == NULL){ 
                    free(arr); 
                    *num = 0;
                    return NULL;
                }
                arr = tmp;
				break;
			}
			list2_node = list2_node->next;
		}
		list1_node = list1_node->next;
	}
	return arr;
}


int list_del_max(LinkList mylist){
	if(NULL == mylist || __is_empty(mylist))
		return -1;
	DataType max = mylist->next->data;
	LinkNode *p = mylist->next;
	while(p != NULL){
		if(p->data > max)
			max = p->data;
		p = p->next;
	}
	list_del(mylist, max);
	return 0;
}

LinkList list_reverse(LinkList mylist){
	if(__is_empty(mylist))
		return NULL;
	LinkNode *node = mylist->next;
	LinkNode *t = NULL;
	while(node->next != NULL){
		t = node->next;
		node->next = t->next;
		
		t->next = mylist->next;
		mylist->next = t;
	}
	return mylist;
}

int list_init(LinkList * mylist){
	*mylist  = malloc(sizeof(LinkNode));
	if(NULL == *mylist)
		return -1;
	(*mylist)->data = 4;
	(*mylist)->next = NULL;

	return 0;
}

LinkNode *__creat_node(const DataType data){
	LinkNode * node = malloc(sizeof(LinkNode));
	if(NULL == node)
		return NULL;
	node->data = data;
	node->next = NULL;
	return node;	
}

int list_insert(LinkList mylist, const DataType data){
	LinkNode *node = __creat_node(data);
	if(NULL == node)
		return -1;
	node->next = mylist->next;
	mylist->next = node;

	return 0;
}

int __is_empty(LinkList mylist){
	return mylist->next == NULL;
}

void list_show(LinkList mylist){
	if(__is_empty(mylist))
		return;
	LinkNode *node = mylist->next;
	while(node != NULL){
		printf("%d ", node->data);
		node = node->next;
	}
	return;
}

int list_del(LinkList mylist, DataType key){
	if(__is_empty(mylist))
		return -1;
	LinkNode *npre = mylist;
	LinkNode *node = mylist->next;

	while(node != NULL){
		if(node->data == key){
			npre->next = node->next;
			node->next = NULL;
			free(node);
			node = NULL;
			return 0;
		}
		npre = node;
		node = node->next;
	}
	return -1;
}


void list_destroy(LinkList *mylist){
	if(*mylist == NULL)
		return;
	while(!__is_empty(*mylist)){
		DataType key = (*mylist)->next->data;
		list_del(*mylist, key);
	}
		free(*mylist);
		*mylist = NULL;
		return;
}
